package first

/*
	统计一个数字在排序数组中出现的次数。

	示例 1:

	输入: nums = [5,7,7,8,8,10], target = 8
	输出: 2
	示例2:

	输入: nums = [5,7,7,8,8,10], target = 6
	输出: 0

	提示：

	0 <= nums.length <= 105
	-109<= nums[i]<= 109
	nums是一个非递减数组
	-109<= target<= 109

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func search(nums []int, target int) int {
	// 给定左右边界l,r、使得(l...r)开区间内包含所有target
	left, right := 0, 0
	i, j := 0, len(nums)-1
	for i <= j {
		mid := (i + j) / 2
		if nums[mid] >= target {
			j = mid - 1
		} else {
			i = mid + 1
		}
	}
	i, j = 0, len(nums)-1
	left = j
	for i <= j {
		mid := (i + j) / 2
		if nums[mid] > target {
			j = mid-1
		} else {
			i = mid+1
		}
	}
	right = i
	return right - left - 1
}
